package from_0_to_50;

import java.util.Arrays;
import java.util.Scanner;

public class Q0010_isMatch {
//     给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
//             '.' 匹配任意单个字符
//              '*' 匹配零个或多个前面的那一个元素
//     所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串

    public static void main(String[] args) {
        StringBuffer a = new StringBuffer(10);
        a.deleteCharAt(a.length()).toString();
        a.length();
        System.out.println("a = " + a);
//            String s = "aaa";
//            String p ="ab*a*c*a";
        String s = "aaa";
        String p = ".*";
        System.out.println("isMatch(s,p) = " + isMatch(s, p));

    }
    public static boolean isMatch(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        boolean[][] dp = new boolean[pLen+1][sLen+1]; // dp[i][j]: true表示 [0,i)和[0,j)可以匹配
        dp[0][0] = true;
        for(int i = 1; i <= pLen; i++){     // i-1: p的真实下标
            for(int j = 0; j < sLen; j++){  //   j: s的真实下标
                System.out.println("j = " + j);
                if(p.charAt(i-1) == '*'){
                    dp[i][0]  = dp[i-1][0] || dp[i-2][0];
                    // *匹配0个：同列上方两格，
                    dp[i][j+1] = ((dp[i-2][j+1] || dp[i-1][j+1])   ||  ((dp[i-1][j] || dp[i][j]) && (p.charAt(i-2) == s.charAt(j)||p.charAt(i-2) == '.')));// 0个 || 1个
                }
                if(p.charAt(i-1) == '.' || p.charAt(i-1) == s.charAt(j)){
                    dp[i][j+1] = dp[i-1][j];
                }
            }
        }
        show(s,p,dp);
        return dp[pLen][sLen];
    }
    public static void show(String s, String p, boolean[][] dp) {
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        System.out.print("\t\t\t");
        for (int i = 0; i < sChars.length; i++) {
            System.out.print(sChars[i]+"\t\t");
        }
        System.out.println();
        for (int i = 0; i <= pChars.length; i++) {
            if(i != 0)
                System.out.print(pChars[i-1]+"\t");
            else
                System.out.print("\t");

            for (int j = 0; j <= sChars.length; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println();
    }
}
